package leetcode.code0449;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Codec implements IDebug {

	// Encodes a tree to a single string.
	public String serialize(TreeNode root) {
		if (root == null) {
			return null;
		}
		StringBuffer ans = new StringBuffer();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			while (size > 0) {
				TreeNode node = queue.poll();
				if (node != null) {
					queue.add(node.left);
					queue.add(node.right);
					ans.append(node.val).append(",");
				} else {
					ans.append("null").append(",");
				}
				size--;
			}

		}
		return ans.substring(0, ans.length() - 1);
	}

	// Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
		if (data == null) {
			return null;
		}
		String[] vals = data.split(",");
		int len = vals.length;
		int p = 0;
		TreeNode root = new TreeNode(Integer.valueOf(vals[p++]));
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (p < len) {
			int size = queue.size();
			while (size > 0 && p < len) {
				TreeNode node = queue.poll();
				String left = vals[p++];
				String right = vals[p++];
				if (!left.equals("null")) {
					TreeNode node1 = new TreeNode(Integer.valueOf(left));
					node.left = node1;
					queue.add(node1);
				}
				if (!right.equals("null")) {
					TreeNode node2 = new TreeNode(Integer.valueOf(right));
					node.right = node2;
					queue.add(node2);
				}
				size--;
			}
		}
		return root;
	}

	@Override
	public void debug4() {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.right.left = new TreeNode(5);
		root.right.right = new TreeNode(6);
		root.right.left.right = new TreeNode(7);
		String s = this.serialize(root);
		System.out.println(s);
		TreeNode node = this.deserialize(s);
		System.out.println("done");
	}

	@Override
	public void debug3() {
		TreeNode root = new TreeNode(0);
		String s = this.serialize(root);
		System.out.println(s);
		TreeNode node = this.deserialize(s);
		System.out.println("done");

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Codec so = new Codec();
		so.debug1();
		so.debug2();
		so.debug3();
//		so.debug4();

	}

}
